1. Field of the Invention
The present invention relates generally to user display interfaces, and more particularly relates to a system and method for dynamic space management of a user display interface which efficiently manages available empty-space during both add and remove operations of full-space rectangles.
2. Background of the Related Art
Computer graphics systems which are commonly used today generally provide a representation of the workspace, or display screen, occupied by the various elements of the scene. For example, in the case of a graphical user interface (GUI), such as a window manager for the Microsoft Windows® operating system, various icons and working windows are placed about the display space. In such an environment, it is often desirable to automatically allocate space for a new or modified object while avoiding intersecting or overlaying other objects which have already been allocated on the workspace. This generally either requires adjusting the size of the new object to fit within a selected space or more desirably, finding an available position on the display which maintains the size and aspect ratio of the object to be placed without overlapping previously placed objects. While several systems and methods for simplistic space management of a display have been used previously, such as simple window managers which use automatic tiling or cascading of objects, these systems have shortcomings.
One aspect of effective space management is the modeling and use of the empty-space which is available on the workspace. One method of modeling the empty-space, such as on a user display, is described in the article “Free Space Modeling for Placing Rectangles without Overlapping” by Bernard et al, which was published in the Journal of Universal Computer Science, 3 (6), pp 703-720, Springer-Verlag, June 1997. Bernard et al. describe a method of computing the free space available on a workspace, representing the free space as a set of empty-space rectangles, and using this representation to determine the placement of a new full-space rectangle on the display space in a non-overlapping manner. The modeling of the free space as a set of largest empty-space rectangles as disclosed by Bernard et al. provides an effective representation of the free space. Bernard et al. also disclose managing the workspace and adding new objects in the context of non-overlapping rectangles. However, Bernard et al. do not address the management of the display when two full-space objects overlap and do not provide a process for efficiently updating the empty-space model upon removal of a full-space rectangle from the display workspace. Accordingly, there remains a need for a dynamic space manager which efficiently models the available free space of a workspace in the presence of overlapping objects and during both add and remove operations affecting the workspace.